package com.kehao.newcoder;

import org.junit.Test;

public class NC21Solution {

    private class ListNode {
        int val;
        ListNode next = null;

        public ListNode(int val) {
            this.val = val;
        }
    }


    public ListNode reverseBetween(ListNode head, int m, int n) {
        ListNode h = new ListNode(0);
        h.next = head;
        ListNode start = head;//开始反转的节点
        ListNode beforeStart = h;
        ListNode end = head;//结束反转的节点
        ListNode afterEnd = end.next;
        for (int i = 0; i < m-1; i++) {
            beforeStart = beforeStart.next;
            start = start.next;
        }

        for (int i = 0; i < n-1; i++) {
            end = end.next;
        }
        afterEnd = end.next;

        end.next = null;
        ListNode[] reverse = reverse(start);
        beforeStart.next = reverse[0];
        reverse[1].next = afterEnd;
        return h.next;
    }

    private ListNode[] reverse(ListNode head) {
        ListNode node = head;
        ListNode h = new ListNode(0);
        ListNode p = head.next;
        while (head!=null){
            head.next = h.next;
            h.next = head;
            head = p;
            if(p!=null) p = p.next;
        }
        return new ListNode[]{h.next,node} ;
    }

    private ListNode init(int[] arr){
        if(arr.length==0){
            return null;
        }
        ListNode head = new ListNode(arr[0]);
        ListNode p = head;
        for (int i = 1; i < arr.length; i++) {
            p.next = new ListNode(arr[i]);
            p = p.next;
        }
        return head;
    }

    @Test
    public void test(){
        ListNode head = init(new int[]{1, 2, 3, 4, 5});
        reverseBetween(head,2,4);
        print(head);
    }

    private void print(ListNode head) {
        while (head!=null){
            System.out.print(head.val+" ");
            head = head.next;
        }
    }
}
